#include"cds_btree.h"
#include<stdlib.h>
#include<stdio.h>
#include<time.h>

//去掉终端行模式,关回显
#define char_input() do{\
    system("stty raw");\
    system("stty -echo");\
}while(0)

//恢复终端行模式,开回显
#define line_input() do{\
    system("stty cooked");\
    system("stty echo");\
}while(0)

#define NR 1000000
//用户数据结构
typedef struct data{
    unsigned long value;//数据域
} data_t;


void travel(unsigned long key, void * data ){
    printf("(%lu) ", ((struct data*)data)->value); 
}

void destroy(void * data){
    printf("free data:%lu ",((data_t*)data)->value);
    free(data);
}

int len=0;
unsigned long keys[NR];

void insert_random_datas(btree_t * tree, unsigned long n){
    time_t t;
    time(&t);
    srand(t);
    len=0;
    for(int i=0;i<n;i++){
        unsigned long value = rand()%NR;
        data_t * data = malloc(sizeof(data_t));
        data->value = 100+value;
        void * ret = btree_insert(tree, data->value, data);
        if(ret){
            i--;
        }else{
            keys[len++] = data->value;
        }
    }
}

int main(void){
    
    btree_t *tree = malloc(sizeof(btree_t));
    //初始化树
    BTREE_INIT(tree); 
    /*
     *  B树示例:
     *
     *      插入顺序: 100, 999, 888, 222, 777, 666, 333, 555, 444, 123, 234, 345, 456, 567,
     *                678, 789, 890, 1125, 1230, 2270, 1953, 2567, 5784, 6543, 4728, 7856, 
     *                5963, 6944, 7869, 895, 764, 392, 297, 891, 982
     *      最终的树形态如下图:
     */
    unsigned long arr[] = { 100, 999, 888, 222, 777, 666, 333, 555, 444, 123, 234, 345, 456, 567,
                     678, 789, 890, 1125, 1230, 2270, 1953, 2567, 5784, 6543, 4728, 7856, 
                     5963, 6944, 7869, 895, 764, 392, 297, 891, 982 };

    
    printf("数组长度:%d\n",sizeof(arr)/sizeof(unsigned long)); 
    //依次插入数组中的数到树中
    for(int i=0;i<sizeof(arr)/sizeof(unsigned long); i++){
        data_t * dptr = malloc(sizeof(data_t));
        dptr->value = arr[i];
        btree_insert(tree,dptr->value, dptr); 
    }
   
    int loop = 1;
    int idx=0;
    while(loop){
        unsigned long key;
        printf("[t]: level travel; [r]: insert more random datas; [s]: search; \n[i]: insert; [d]: delete; [c]: clear; [q]: quit; [m]: middle order travel; \n请输入:\n");
        char_input();
         
        char ch;
        do{
            ch = getchar();
        }while(ch==13 || ch==10);
     
        line_input();
        switch( ch ){
            
            case 's': //搜索
                printf("输入key:\n");
                scanf("%lu",&key);
                data_t * data  = (data_t *)btree_search(tree, key);
                if(data){
                    printf("找到了数据[%lu]\n",data->value);
                }else{
                    printf("没找到key[%lu]\n",key);
                }
                break;
            case 'i': //插入
                {
                
                printf("输入要插入到数:\n");
                scanf("%lu",&key);
                //key = arr[idx++];
                data_t * pd = malloc(sizeof(data_t));
                pd->value = key;
                printf("正在插入%lu\n",key);
                btree_insert(tree,pd->value, pd); 
                }
                break;
            case 'm': // middle order travel
                btree_travel_middle(tree,travel); 
                printf("一共有%d个数\n",tree->size);
                break;
            case 'r': //插入多个随机数
                {
                    printf("请输入要插入的数量(<=%lu):\n",NR);
                    scanf("%lu",&key);
                    insert_random_datas(tree, key);                 
                }
                break;
            case 'd': //删除
                {
                    printf("请输入要删除的key:\n");
                    scanf("%lu",&key);
                    data_t * dd = (data_t*)btree_del(tree, key);
                    printf("删除了数据:%lu\n",dd->value);
                }
                break;
            case 'D': //测试大量删除
                {
                    unsigned long i=0;
                    while(i<len){
                        data_t * dd = (data_t*)btree_del(tree,keys[i]);
                        i++;
                        if(tree->root==NULL)break;
                    }
                    printf("一共删除了%lu个数据,tree->root=%p\n",i,tree->root);
                }
                break;
            case 'c': //清空树
                btree_clear(tree, destroy); 
                putchar('\n');
                break;
            case 't': //层次遍历树
                btree_print_tree(tree);
                putchar('\n');
                printf("一共有%d个数\n",tree->size);
                break;
            case 'q': //退出程序
                loop = 0;
                break;
        }
    }

    return 0;
}
